package com.buddy.leetcode._17;

import java.util.Arrays;

/**
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
 * 找出 nums 中的三个整数，使得它们的和与 target 最接近。
 * 返回这三个数的和。假定每组输入只存在唯一答案。
 * 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
 * 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
 */
public class ThreeSumClosest {

    /**
     * 将数组排序，开始遍历数组,先确定一个数，
     * 然后用两个指针left和right来滑动寻找另外两个数，每确定两个数，我们求出此三数之和，
     * 然后算和给定值的差的绝对值存在newDiff中，然后和diff比较并更新diff和结果closest即可
     * @param nums
     * @param target
     * @return
     */
    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closest = nums[0]+nums[1]+nums[2];
        int diff = Math.abs(target-closest);//定义一个变量diff用来记录差的绝对值
        int sum,newDiff;
        for (int i=0;i<nums.length -2;++i){
            int left = i+1,right=nums.length-1;
            while (left<right){
                sum = nums[i]+nums[left]+nums[right];
                newDiff = Math.abs(target-sum);
                if (newDiff < diff){
                    closest = sum;
                    diff = newDiff;
                }
                if (sum < target){
                    ++left;
                }else{
                    --right;
                }
            }
        }
        return closest;
    }

    public static void main(String[] args){
       int[] nums = new int[]{0,2,1,-3};
       System.out.println(threeSumClosest(nums,1));
    }
}
